#include <iostream>

struct Node {
  Node *pNext;
  int data;
  Node(int d): pNext(0), data(d) {}
};

Node *deleteNode(Node *pHead, int d) {
  Node *n = pHead;
  if (n->data == d) {
    n = n->pNext;
    // delete head;
    pHead = n;
    return pHead;
  }
  
  while (0 != n->pNext) {
    if (n->pNext->data == d) {
      n->pNext = n->pNext->pNext;
      return pHead;
    }
    n = n->pNext;
  }
}

void printList(Node *n)
{
  while(n != 0) {
    std::cout << n->data << " ";
    n = n->pNext;
  }
  
  std::cout << std::endl;
}

// 2.1
Node *deleteAll(Node *pHead, int d)
{
  if (0 == pHead) return 0;
  Node *pRes = pHead;
  
  Node *pN = pHead;
  
  while (0 != pN->pNext) {
    if (pN->pNext->data == d) {
      if (pN->pNext == pRes){
	pRes = pN->pNext->pNext;
      }
      
      pN->pNext = pN->pNext->pNext;
    }
    pN = pN->pNext;
    if(0 == pN) break;
  }
  
  return pRes;
}

void removeDuplicates(Node *pNode)
{
  if (0 == pNode) return;
  
  Node *pN = pNode;
  
  while (0 != pN) {
    pN = deleteAll(pN->pNext, pN->data);
  }  
}

// 2.2
Node *reverseList(Node *pNode)
{
  Node *pN = pNode;
  Node *pPrev = 0;
  while (0 != pN) {
    Node *pNode = new Node(pN->data);
    pNode->pNext = pPrev;
    pPrev = pNode;
    pN = pN->pNext;
  }
  return pPrev;
}

int nToLast(Node *pNode, int n)
{
  Node *pReverse = reverseList(pNode);
  Node *pN = pReverse;
  
  for (int i=0; i < n-1 && pN!=0; ++i) {
    pN = pN->pNext;
  }
  
  if (pN != 0)
    return pN->data;
  
  return 0;
}

// 2.3
void shiftLeft(Node *pHead)
{
  if (0 == pHead) return;
  Node *pN = pHead;
  Node ** ppPrevNext = 0;
  while (0 != pN->pNext) {
    pN->data = pN->pNext->data;
    ppPrevNext = &(pN->pNext);
    pN = pN->pNext;
  }
  
  if (0 != ppPrevNext) 
    *ppPrevNext = 0;
    
  
}

// 2.4
Node *addLists(Node *pL1, Node *pL2, int carry)
{
  if(0 == pL1 && 0 == pL2 && 0 == carry) //recu
    return 0;
   
  Node *pNode = new Node(carry);
  Node *pL1Next = 0;
  Node *pL2Next = 0;
  
  if(0 != pL1) {
    pNode->data += pL1->data;
    pL1Next = pL1->pNext;
  }
  
  if(0 != pL2) {
    pNode->data += pL2->data;
    pL2Next = pL2->pNext;
  }
  
  carry = pNode->data / 10;
  pNode->data %= 10;
  pNode->pNext = addLists(pL1Next, pL2Next, carry);
  
  return pNode;
}

// 2.5
#include <set>
Node *findBeginning(Node *pNode)
{
  std::set<Node *> nodes;
  
  while (0 != pNode) {
    if(nodes.count(pNode) > 0) {
      return pNode;
    }else {
      nodes.insert(pNode);
      pNode = pNode->pNext;
    }
  }
  return 0;
}

int main(int argc, char *argv[])
{
  Node n1(1);
  Node n2(2);
  Node n3(1);
  Node n4(4);
  Node n5(3);
  Node n6(2);
  Node n7(4);
  n1.pNext = &n2;
  n2.pNext = &n3;
  n3.pNext = &n4;
  n4.pNext = &n5;
  n5.pNext = &n6;
  n6.pNext = &n7;

#if 0
  printList(&n1);
  printList(deleteNode(&n1, 3));
  printList(deleteNode(&n1, 1));
#endif

#if 0
// 2.1
  printList(&n1);
  removeDuplicates(&n1);
  printList(&n1);
#endif

#if 0
// 2.2
  printList(&n1);
  printList(reverseList(&n1));
  std::cout << nToLast(&n1, 3) << std::endl;
  std::cout << nToLast(&n1, 2) << std::endl;
  std::cout << nToLast(&n1, 100) << std::endl;
#endif
  
#if 0
// 2.3
  printList(&n1);
  shiftLeft(&n4);
  printList(&n1);
#endif

#if 0
// 2.4
  Node n10(0), n20(3), n30(1), n40(5), n50(6);;
  Node n11(1), n22(5), n33(9), n44(2);
  n10.pNext = &n20; n20.pNext = &n30; n30.pNext = &n40;n40.pNext = &n50;
  n11.pNext = &n22; n22.pNext = &n33; n33.pNext = &n44;
  
  printList(&n10);
  printList(&n11);
  printList(addLists(&n10, &n11, 0));
#endif

#if 1
  Node A(1), B(2), C(3), D(4), E(5);
  A.pNext = &B;
  B.pNext = &C;
  C.pNext = &D;
  D.pNext = &E;
  E.pNext = &C;
  std::cout << findBeginning(&A)->data << std::endl;
#endif
  
  return 0;
}